#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

void InsertSort(int* a, size_t size)
{
	int tmp = 0;

	for (int i = 1; i < size; i++)
	{
		tmp = i;
		for (int j = i - 1; j >= 0; j--)
		{
			if (a[tmp] < a[j])
			{
				swap(a[tmp], a[j]);
				tmp = j;
			}
			else
			{
				break;
			}
		}
	}

}

void SelectSort(int* a, size_t size)
{
	int begin = 0;
	while (begin < size - 1)
	{
		int min = begin;
		for (int i = begin; i < size; i++)
		{
			if (a[i] < a[min])
			{
				min = i;
			}
		}

		swap(a[begin], a[min]);

		begin++;
	}

}

void BubbleSort(int* a, size_t size)
{
	for (int i = 0; i < size - 1; i++)
	{
		bool x = false;
		for (int j = 1; j < size - i; j++)
		{
			if (a[j] < a[j - 1])
			{
				swap(a[j], a[j - 1]);
				x = true;
			}
		}

		if (x == false)
		{
			break;
		}
	}


}

int main()
{
	int a[] = { 9,8,7,6,5,4,3,2,1 };
	
	size_t size = sizeof(a) / sizeof(a[0]);

	InsertSort(a, size);

	for (int i = 0; i < size; i++)
	{
		cout << a[i] << " ";
	}


	return 0;
}